package com.zk.algorithm.tree;

import com.zk.algorithm.bean.TreeNode;
import com.zk.algorithm.factory.TreeFactory;

/**
 * @author zk
 */
public class BalancedBinaryTree {

    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;

        return
                // 节点自身是否平衡? 看高度差
                isBalanced(height(root.left), height(root.right)) &&
                        // 左子树是否平衡
                isBalanced(root.left) &&
                        // 右子树是否平衡
                isBalanced(root.right);
    }

    private boolean isBalanced(int leftHeight, int rightHeight) {
        return Math.abs(leftHeight - rightHeight) <= 1;
    }

    private int height(TreeNode root) {
        if (root == null)
            return 0;

        return Math.max(height(root.left), height(root.right)) + 1;
    }

    public static void main(String...args) {
        System.out.println(new BalancedBinaryTree().isBalanced(TreeFactory.buildTree(new Integer[]{
                3,9,20,null,null,15,7
        })));

        System.out.println(new BalancedBinaryTree().isBalanced(TreeFactory.buildTree(new Integer[]{
                1,2,2,3,3,null,null,4,4
        })));
    }

}
